#!/usr/bin/python
# -*- coding: utf-8 -*-

import Image
import sys

#最大連続谷取得
def get_maxspace(list, threhold):
        count = 0
        hi_active = False
        max_count = 0

        for v in list:
                if v > threhold:
                        if max_count < count:
                                max_count = count
                        count = 0
                else:
                        count = count + 1
        return max_count

#リスト区切り
def split_sum(list, threshold, low_width):
        hi_count = 0
        low_count = 0
        hi_active = False
        count = 0

        for v in list:
                if v > threshold:
                        count = 0
                        if ( not hi_active ):
                                hi_active = True
                                hi_count = hi_count + 1

                else:
                        count = count + 1
                        if ( count <= low_width):
                                continue
                        if ( hi_active):
                                hi_active = False
                                low_count = low_count + 1


        return hi_count

#最適な
def get_optimal_threshold_width(list):
	#関数をきく
        max_threhold = int(max(list)/8)

        #f_list (threhold, splitcount)
        f_list = []
        for idx in range(2,max_threhold):
                f_list.append((idx, split_sum(list, idx, 3)))

        #最大のsplitcountでthreholdを決める
        #threhold(first)
        threhold = 0
        max_splitcount = 0
        for idx in range(len(f_list)):
                if max_splitcount < f_list[idx][1]:
                        max_splitcount = f_list[idx][1]
                        threhold = f_list[idx][0]

        #print "first threhold: ",threhold
        #print "max threhold:", int(max(list)/8)

        #width(first)
        #print "max width:" , get_maxspace(list, threhold)

        #s_list (width, splitcount)
        #計算範囲3 ~ 最大width/2
        s_list = []
        for w in range(3, int(get_maxspace(list, threhold)/2)):
                s_list.append((w, split_sum(list, threhold, w)))

	#頻度が高いsplitcountでwidthを決める
        #splitcountが平均以下の値を除く
        mid_splitcount = int(max(map(lambda x: x[1], s_list))/2)

        # t_list ( width, splitcount )
        # 中値以上のリスト
        t_list = []
        for w, c in s_list:
                if c >= mid_splitcount :
                        t_list.append((w, c))

        #dictionary作成
        dic = {}
        for w, c in t_list:
                if not dic.has_key(c):
                        dic[c] = 1
                else:
                        dic[c] = dic[c] + 1
        #最適なwidth
	opt_width = 0
        tsc, tc = reduce( lambda a,b: a if a[1] > b[1] else b ,dic.items())
	for w, c in s_list[::-1]:
		if tsc == c:
			opt_width = w
			break

        #print "first threhold: ",threhold
	return (opt_width, threhold)

#行ごとの集計
def get_horizontal_sum(pix, iw, ih):
	list = []
	for y in range(ih):
		cnt = 0
                for x in range(iw):
                        if ( pix[x, y] == 0 ):
                                cnt = cnt + 1
		list.append(cnt)
	return list


#行ブロック分け
def get_horizontal_blocks(list, opt_width, opt_threshold):
	#threshold適用
	new_list = []
	for v in list:
		if v <= opt_threshold:
			new_list.append(0)
		else:
			new_list.append(v - opt_threshold)	
	
	#block分け
	blocks = []
	count = 0
	for idx in range(len(new_list)):
		if new_list[idx] > 0:
			count = count + 1
		else:
			if count > 0 :
				blocks.append((idx-count, idx))
			count = 0

	if count > 0:
		blocks.append((idx-count, idx))	

	#block結合
	new_blocks = []
	new_idx = 0
	for idx in range(len(blocks)):
		if idx == 0:
			new_blocks.append(blocks[idx])
			continue
		
		if blocks[idx][0] - new_blocks[new_idx][1] < opt_width:
			new_blocks[new_idx] = (new_blocks[new_idx][0], blocks[idx][1])
		else:
			new_blocks.append(blocks[idx])
			new_idx = new_idx + 1
		
		
	return new_blocks
				
	









	
